package sendback;

/**
 * 递归合集
 */
public class SendBack {
    public static void main(String[] args) {
        // 阶乘
        System.out.println(factorial(3));
        // 斐波那契数列
        System.out.println(fibonacciSequence(6));
        // 杨辉三角
        System.out.println(yhTriangle(1, 4));
    }

    /**
     * 阶乘的实现 1 * 2 * 3 * n
     *
     * @return
     */
    public static long factorial(int n) {
        if (n == 1) {
            return 1;
        }
        return (long) n * (n - 1);
    }

    /**
     * 斐波那契数列
     * 1,1,2,3,5,8,13,21,34,
     * f(0) = 0 f(1) = 1 fn = f(n - 1) + f(n - 2)
     *
     * @param n
     * @return
     */
    public static long fibonacciSequence(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        return fibonacciSequence(n - 1) + fibonacciSequence(n - 2);
    }

    /**
     * 杨辉三角，找出 x , y 位置上的值
     *    1
     *   1 1
     *  1 2 1
     * 1 3 3 1
     * 终止条件： x >= 0, y >= 0
     * f(0, 0) = f(0 , 1) = f(1, 0) = 1
     * 同一行开头和结尾 = 1
     * @param x
     * @param y
     * @return
     */
    public static int yhTriangle(int x, int y) {
        if (y < 0 || x > y) {
            return -1;
        }
        if (y == 0 || y == 1 || x == 0 || x == y) {
            return 1;
        } else {
            return yhTriangle(x - 1, y - 1) + yhTriangle(x, y - 1);
        }
    }
}
